#include "../include/greedy.h"
#include <stdlib.h>

/**
 * 比较函数：按单位价值（价值/重量）降序排序
 * @param a 第一个物品
 * @param b 第二个物品
 * @return 比较结果
 */
static int compare_items(const void* a, const void* b) {
    const Item* item1 = (const Item*)a;
    const Item* item2 = (const Item*)b;
    double ratio1 = item1->value / item1->weight;
    double ratio2 = item2->value / item2->weight;
    
    // 按单位价值降序排序
    if (ratio1 > ratio2) return -1;
    if (ratio1 < ratio2) return 1;
    return 0;
}

/**
 * 贪心算法求解0-1背包问题
 * 时间复杂度：O(n log n)，空间复杂度：O(n)
 * @param items 物品数组
 * @param n 物品数量
 * @param capacity 背包容量
 * @param result 结果结构体指针
 */
void greedy_knapsack(Item* items, int n, int capacity, Result* result) {
    // 初始化结果
    result->total_value = 0;
    result->selected_count = 0;
    result->time_taken = 0;
    result->memory_used = 0;
    result->selected_items = NULL;

    // 记录开始时间
    clock_t start = clock();

    // 创建物品副本并排序
    Item* sorted_items = (Item*)malloc(n * sizeof(Item));
    if (!sorted_items) {
        printf("Memory allocation failed\n");
        return;
    }
    memcpy(sorted_items, items, n * sizeof(Item));
    qsort(sorted_items, n, sizeof(Item), compare_items);

    // 分配结果数组
    result->selected_items = (int*)malloc(n * sizeof(int));
    if (!result->selected_items) {
        printf("Memory allocation failed\n");
        free(sorted_items);
        return;
    }

    // 贪心选择过程
    double remaining_capacity = capacity;
    for (int i = 0; i < n; ++i) {
        if (sorted_items[i].weight <= remaining_capacity) {
            // 如果当前物品可以放入背包
            result->selected_items[result->selected_count++] = sorted_items[i].id;
            result->total_value += sorted_items[i].value;
            remaining_capacity -= sorted_items[i].weight;
        }
    }

    // 记录结束时间和内存使用
    clock_t end = clock();
    result->time_taken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000;
    result->memory_used = n * (sizeof(Item) + sizeof(int));  // sorted_items和selected_items数组

    // 释放内存
    free(sorted_items);
} 